package main

import "fmt"

/*
对称的二叉树
请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。
例如，二叉树[1,2,2,3,4,4,3] 是对称的。
  1
 / \
 2  2
/ \ / \
3 4 4 3
但是下面这个[1,2,2,null,3,null,3] 则不是镜像对称的:
  1
 / \
 2  2
 \  \
 3  3

示例 1：
输入：root = [1,2,2,3,4,4,3]
输出：true

示例 2：
输入：root = [1,2,2,null,3,null,3]
输出：false
*/

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

//猪鼻暴力 还有问题
/*
func isSymmetric(root *TreeNode) bool {
	//先层次遍历
	var res [][]int
	if root == nil {
		return true
	}
	//利用队列
	queue := []*TreeNode{root}
	var level = 0
	for len(queue) != 0 {
		//利用临时队列，暂存每个节点的左右子树
		var temp []*TreeNode
		//只需考虑在同一层上追加元素
		res = append(res, []int{})
		//遍历队列，追加队列元素到切片同一层，追加队列元素左右子树到临时队列
		for _, v := range queue {
			res[level] = append(res[level], v.Val)
			if v.Left != nil {
				temp = append(temp, v.Left)
			}
			if v.Right != nil {
				temp = append(temp, v.Right)
			}
		}
		//层级加1，队列重新复制为队列的左右子树集
		level++
		//队列赋值
		queue = temp
	}
	//此时已经将二叉树按层次序列放入二维切片res中
	fmt.Println(res)
	for _, v := range res { //依次判断每层是否对称
		var left, right = 0, len(v) - 1
		for left <= right {
			if v[left] != v[right] {
				return false
			} else {
				left++
				right--
			}
		}
	}
	return true
}
*/

//递归
/*
如果同时满足下面的条件，两个树互为镜像：
1.它们的两个根结点具有相同的值
2.每个树的右子树都与另一个树的左子树镜像对称

通过「同步移动」两个指针的方法来遍历这棵树，p指针和 q指针一开始都指向这棵树的根，随后 p右移时，q左移，
p左移时，q右移。每次检查当前 p和 q节点的值是否相等，如果相等再判断左右子树是否对称。
*/
func isSymmetric(root *TreeNode) bool {
	return check(root, root)
}

func check(p, q *TreeNode) bool {
	if p == nil && q == nil {
		return true
	}
	if p == nil || q == nil {
		return false
	}
	return p.Val == q.Val && check(p.Left, q.Right) && check(p.Right, q.Left)
}

//层次遍历
func isSymmetric2(root *TreeNode) bool {
	if root == nil {
		return true
	}
	queue := []*TreeNode{root}
	for len(queue) > 0 { // 层序遍历
		l := len(queue)
		fmt.Println(l)
		for i, j := 0, l-1; i < j; i, j = i+1, j-1 { // 判断本层是不是回文串
			if queue[i] == queue[j] || (queue[i] != nil && queue[j] != nil && queue[i].Val == queue[j].Val) {
				// 本层是回文串，满足条件
			} else { // 本层不是回文串
				return false
			}
		}
		for i := 0; i < l; i++ { // 将每个节点的孩子放入队列
			if queue[i] != nil {
				queue = append(queue, queue[i].Left)
				queue = append(queue, queue[i].Right)
			}
		}
		queue = queue[l:] // 本层节点出队
	}
	return true
}

func main() {
	A := &TreeNode{Val: 1}
	A.Left = &TreeNode{Val: 2}
	A.Right = &TreeNode{Val: 2}
	fmt.Println(isSymmetric(A))
}
